package com.fengye.algorithms.leecode.dp;

/**
 * @author loupf50246
 * @date 2023/7/21 17:01
 */
public class Largst1BorderedSquare1139 {
    public static void main(String[] args) {

    }

    public static int largst1BorderedSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // dp[i][j][0]: (i,j)横向连续1的个数
        // dp[i][j][1]: (i,j)竖向连续1的个数
        int[][][] dp = new int[m+1][n+1][2];
        for (int i = 1; i <= m;i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                // 如果是1，就计算横向和竖向是1的个数
                dp[i][j][0] = dp[i][j-1][0] + 1;
                dp[i][j][1] = dp[i-1][j][1] + 1;
            }
        }
        // 记录正文形的最大长度
        int maxSize = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 沿着当前坐标往上和往左找出最短距离，暂时看做是正方形的边长
                // 正方形的具体边长还要看上边和左边和长度，所以这里要判断一下
                int curSize = Math.min(dp[i][j][0], dp[i][j][1]);
                // 比maxSize小就不看了
                if (curSize <= maxSize) {
                    continue;
                }
                // curSize可以认为是正方形下边和右边的长度
                // 还需要根据正方形上边和左边的长度来确认是不是满足正方形的条件
                for (; curSize > maxSize; curSize--) {
                    // 判断正方形的左边和上边的长度是否大于curSize,如果不大于，我们就缩小
                    // 正方形的长度curSize,然后继续判断
                    if (dp[i][j-curSize + 1][1] >= curSize
                            && dp[i - curSize + 1][j][0] >= curSize) {
                        maxSize = curSize;
                        // 更短的就没必要考虑了
                        break;
                    }
                }
            }
        }
        return maxSize * maxSize;
    }
}
